package cn.mayday.algorithms.year2021.month1.分治动态规划算法;

/**
 * 剑指 Offer 42. 连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 * <p>
 * 简单
 *
 * @author Mayday05
 * @date 2021/5/12 16:52
 */
public class Offer042MaxSubArray {

    public static void main(String[] args) {

    }

    // 方法一：动态规划
    // 主要思想是：推导出 假设dp[i]表示以nums[i]为结尾的连续子数组的最大和
    //           若dp[i-1]<=0，执行dp[i] = num[i]即可（说明前面的都是累赘，还不如我）
    //           若dp[i-1]>0， 执行dp[i] = dp[i-1] + num[i] （好歹有点用）

    //           初始状态 dp[0] = nums[0]


    // 时间复杂度: 线性遍历数组nums，O(N)
    // 空间复杂度: 直接在原数组上赋值，省去dp列表使用的额外空间，空间复杂度从o(n)->o(1)
    public int maxSubArray(int[] nums) {

        int result = nums[0]; // 保存临时最大值
        for (int i = 1; i < nums.length; i++) {
            // 开始由dp[i-1]，推倒dp[i]
            if (nums[i - 1] < 0) {
                nums[i] = nums[i]; // 这里使用了nums[i]保存dp[i],节省空间
            } else {
                nums[i] = nums[i - 1] + nums[i];
            }
            if (nums[i] > result) {
                result = nums[i]; // 更新： 比较dp[i]和上一次的结果，谁大取谁
            }
        }
        return result;
    }

}
